package com.itdfq.algorithm.divideAndConquer;

/**
 * @Author: QianMo
 * @Date: 2021/11/18 10:52
 * @Description: 分治算法
 *
 * <p/>
 * 分：将整个问题划分成多个相对独立、涉及数据量更少的小问题，有些小问题还可以划分成很多更小的问题，直至每个问题都不可再分；
 * 治：逐个解决所有的小问题；
 * 合并：将所有小问题的解决方案合并到一起，找到解决整个问题的方案。
 *
 * 会耗费较多的时间和内存空间
 *
 * 求最大值 最小值问题
 */
public class Demo1 {
    public static int getMax(int [] arr,int left,int right) {
        //如果数组不存在或者数组内没有元素
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //如果查找范围中仅有 2 个数字，则直接比较即可
        if(right - left <=1) {
            if(arr[left] >= arr[right]) {
                return arr[left];
            }
            return arr[right];
        }
        //等量划分成 2 个区域
        int middle = (right-left)/2 + left;
        int max_left = getMax(arr,left,middle);
        int max_right = getMax(arr,middle+1,right);
        if(max_left >= max_right) {
            return max_left;
        }else {
            return max_right;
        }
    }
    public static void main(String[] args) {
        int [] arr = new int[] { 3,7,2,1 };
        int max = getMax(arr,0,3);
        System.out.println("最大值："+max);
    }
}
